package fast_slow_pointer;

/**
 * @Description 876. 链表的中间结点 https://leetcode.cn/problems/middle-of-the-linked-list/
 * @Author Firenut
 * @Date 2023-02-15 16:09
 */
public class T876_middleNode {
    public ListNode middleNode(ListNode head) {
        if(head.next==null){
            return head;
        }

        // fast指针每次移动2个节点，slow指针每次移动一个节点;
        // 当fast指针到达链表的尾部时，所走过的次数是length/2,也即fast指针和slow指针的距离为length/2
        // 所以slow指针必然指向的是链表的中点
        // 注意题目中，如果有两个中间节点，返回第一个还是第二个
        // 如果返回的是第一个,那么fast指针的移动的条件是 while(fast.next!=null&&fast.next.next!=null)
        // 这个结论可以记下来
        ListNode fast=head,slow=head;
        while(fast!=null&&fast.next!=null){// 注意fast指针的移动条件
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }
}


class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
